#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 10

#define UP 1
#define DOWN 2
#define RIGHT 3
#define LEFT 4
#define UNABLE 0

void generate_random_walk(char walk[N][N]);
void print_array(char walk[N][N]);
int random_choice(int direction[]);

int main(void) {
    char walk[N][N];

    generate_random_walk(walk);
    print_array(walk);

	return 0;
}

int random_choice(int direction[]) {
	int able_direction[4] = { 0 }, index = 0;

	for (int i = 0; i < 4; i++)
	{
		if (direction[i]) {
			able_direction[index++] = direction[i];
		} else {
			break;
		}
	}

	if (index) {
		return(able_direction[rand() % index]);
	}
	else {
		return UNABLE;
	}
}

void generate_random_walk(char matrix[N][N]) {
	char ch = 'A';
	int x = 0, y = 0, index;
	int direction[4] = { UNABLE }, next_direction;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            matrix[i][j] = '.';
        }
    }

	matrix[x][y] = ch;

	srand(time(NULL));

	while (ch < 'Z') {
		index = 0;
		// 将可用方向列表重置为全不可用
		for (int i = 0; i < 4; i++)
		{
			direction[i] = UNABLE;
		}

		// 可向上
		if (x > 0 && matrix[x - 1][y] == '.') {
			direction[index++] = UP;
		}

		// 可向下
		if (x < N - 1 && matrix[x + 1][y] == '.') {
			direction[index++] = DOWN;
		}

		// 可向左
		if (y > 0 && matrix[x][y - 1] == '.') {
			direction[index++] = LEFT;
		}

		// 可向右
		if (y < N - 1 && matrix[x][y + 1] == '.'){
			direction[index++] = RIGHT;
		}
		
		// 随机挑选一个方向，然后把相应方向上的位置填上值
		if (next_direction = random_choice(direction))
		{
			switch (random_choice(direction))
			{
			case UP:
				x -= 1;
				break;
			case DOWN:
				x += 1;
				break;
			case LEFT:
				y -= 1;
				break;
			case RIGHT:
				y += 1;
				break;
			}

			matrix[x][y] = ++ch;
		}
		else {
			break;
		}
	}
}

void print_array(char matrix[N][N]) {
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			printf("%c ", matrix[i][j]);
		}
		printf("\n");
	}
}
